/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._698;

/**
 * 给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
 * <p>
 * 示例 1：
 * <p>
 * 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
 * 输出： True
 * 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
 *  
 * <p>
 * 注意:
 * <p>
 * 1 <= k <= len(nums) <= 16
 * 0 < nums[i] < 10000
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._698
 * @ClassName: PartitionToEqual
 * @Author: linyaonan
 * @Date: 2020/1/16 16:46
 */
public class PartitionToEqual {

    public boolean canPartitionKSubsets(int[] nums, int k) {
        // 一个分组直接可以实现
        if (k == 1) {
            return true;
        }
        int allCount = 0;
        int max = 0;
        for (int num : nums) {
            allCount += num;
            max = Math.max(max, num);
        }
        // 不能除尽
        if (allCount % k != 0) {
            return false;
        }
        // 每一组的和
        int v = allCount / k;
        // 存在一个超过每一组值的超大值，这个值无法组成合适的组
        if (max > v) {
            return false;
        }
        boolean[] used = new boolean[nums.length];
        return bT(nums, k, v, 0, 0, used);
    }

    /**
     * 回溯
     * @param nums
     * @param k
     * @param t
     * @param cur
     * @param start
     * @param used
     * @return
     */
    private boolean bT(int[] nums, int k, int t, int cur, int start, boolean[] used) {
        // 已经组成
        if (k == 0) {
            return true;
        }
        // 一组组成，组下一组
        if (cur == t) {
            return bT(nums, k - 1, t, 0, 0, used);
        }
        for (int i = start; i < nums.length; i++) {
            if (!used[i] && cur + nums[i] <= t) {
                used[i] = true;
                if (bT(nums, k, t, cur + nums[i], i + 1, used)) {
                    return true;
                }
                used[i] = false;
            }
        }
        return false;
    }

}
